package com.wfm.leetcode.editor.cn;

import com.wfm.common.ListNode;

/**
 * 两两交换链表中的节点
 * 2025-02-26 15:15:24
 *
 * 方法二：迭代
 * 定义3个指针，temp、node1,、node2其中temp为虚拟头结点，node1为当前节点，node2为当前节点的下一个节点
 * 时间复杂度O(n)，空间复杂度O(1)
 */
class SwapNodesInPairs {

    //leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        // 迭代
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode pre = dummy;
        while (pre.next != null && pre.next.next != null) {
            ListNode cur = pre.next;
            ListNode next = pre.next.next;
            pre.next = next;
            cur.next = next.next;
            next.next = cur;
            pre = cur;
        }
        return dummy.next;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) {
        Solution solution = new SwapNodesInPairs().new Solution();
        
    }
}